The present invention relates to security technology, and particularly relates to a message processing method using an operation on an elliptic curve.
Elliptic curve cryptosystems belong to a kind of public key cryptosystem proposed by N. Koblitz and V. S. Miller. The public key cryptosystem includes information called a public key, which may be made generally open to the public, and secret information called a private key, which must be kept concealed. The public key is used for encryption or signature verification of a given message, and the private key is used for decryption or signature generation of the given message.
The private key in the elliptic curve cryptosystem is carried by a scalar value. In addition, the security of the elliptic curve cryptosystem results from difficulty in solving an elliptic curve discrete logarithm problem. The elliptic curve discrete logarithm problem means a problem of obtaining a scalar value d when there are provided a point P which is on an elliptic curve and a point dP which is a scalar multiple of the point P.
Any point on the elliptic curve designates a set of numbers satisfying a defining equation of the elliptic curve. An operation using a virtual point called the point at infinity as an identity element, that is, addition on the elliptic curve is defined all over the points on the elliptic curve. Then, addition of a point to the point itself on the elliptic curve is particularly called doubling on the elliptic curve.
Addition of two points on an elliptic curve is calculated as follows. When a straight line is drawn through the two points, the straight line intersects the elliptic curve at a third point. The point symmetric to this third intersecting point with respect to the x-axis is defined as a point resulting from the addition. For example, in the case of a Montgomery-form elliptic curve, the addition of a point (x1, y1) and a point (x2, Y2), that is,(x3, y3)=(x1, y1)+(x2, y2)is calculated and obtained by:x3=B((y2−y1)/(x2−x1))2−A−x1−x2  (Equation 1)y3=((y2−y1)/(x2−x1))(x1−x3)−y1  (Equation 2)Here, A and B designates coefficients of the following defining equation of the Montgomery-form elliptic curve.By2=x3+Ax2+x  (Equation 3)
Doubling a point on an elliptic curve is calculated as follows. When a tangent line is drawn at a point on an elliptic curve, the tangent line intersects the elliptic curve at another point. The point symmetric to this intersecting point with respect to the x-axis is defined as a point resulting from the doubling. Performing addition on a certain point a specific number of times is called scalar multiplication. The result of the scalar multiplication is called a scalar-multiplied point, and the number of times is called a scalar value.
The difficulty in solving the elliptic curve discrete logarithm problem has been established theoretically while information (computation time, power consumption and the like) involved in secret information such as a private key may leak out in the processing of encryption in real mounting. Thus, there has been proposed an attack method called side channel attack in which the secret information is recovered on the basis of the leak information.
Side channel attack on elliptic curve cryptosystems is disclosed in:
Document 1: J. Coron, Resistance against Differential Power Analysis for Elliptic Curve Cryptosystems, Cryptographic Hardware and Embedded Systems: Proceedings of CHES '99, LNCS 1717, Springer-Verlag, (1999) pp. 292-302.
In the elliptic curve cryptosystems, encryption, decryption, signature generation or signature verification of a given message have to be carried out with an elliptic curve operation. Particularly, calculation of scalar multiplication on an elliptic curve is used in cryptographic processing using a scalar value as secret information.
A countermeasure against side channel attack on elliptic curve cryptosystems is disclosed in:
Document 2: K. Okeya and K. Sakurai, Power Analysis Breaks Elliptic Curve Cryptosystems even Secure Against the Timing Attack, Progress in Cryptology—INDOCRYPT 2000, LNCS 1977, Springer-Verlag, (2000), pp. 178-190.
There is proposed a method using a Montgomery-form elliptic curve and randomizing points on the given elliptic curve in scalar multiplication on the elliptic curve to thereby safeguard against side channel attack.
With the development of information communication networks, cryptographic techniques have been indispensable elements for concealment or authentication about electronic information. Speeding up is demanded along with the security of the cryptographic techniques. The elliptic curve discrete logarithm problem is so difficult that elliptic curve cryptosystems can make key length shorter than that in RSA (Rivest-Shamir-Adleman) cryptosystems basing their security on the difficulty of factorization into prime factors. Thus, the elliptic curve cryptosystems open the way to comparatively high-speed cryptographic processing. However, the processing speed is not always high enough to satisfy smart cards which have restricted throughput or servers which have to carry out large volumes of cryptographic processing. It is therefore demanded to further speed up the processing in cryptosystems.
Indeed the aforementioned technique is effective as a countermeasure against side channel attack, but there is no consideration for further speeding up the processing.